package zuochengyun;

import java.util.LinkedList;

public class GetSubArrayCount {
	public static int getNum(int[] array, int sum) {
		if (array == null || array.length <= 0) {
			return 0;
		}
		//qMax记录的是array[i...j]中的最大值，qMin记录的是最小值
		LinkedList<Integer> qMax = new LinkedList<>();
		LinkedList<Integer> qMin = new LinkedList<>();
		int i = 0, j = 0;
		int result = 0;
		for (; i < array.length; i++) {
			for (;j < array.length; j++) {
				while(!qMin.isEmpty() && array[qMin.peekLast()] >= array[j]){
					qMin.pollLast();
				}
				qMin.addLast(j);
				while(!qMax.isEmpty() && array[qMax.peekLast()] <= array[j]){
					qMax.pollLast();
				}
				qMax.addLast(j);
				//如果array[i...j]中的最大值减最小值大于sum，由于所有包含array[i...j]的数组
				//最大值一定比它的要大等，最小值一定要比它的小等。所以就是所有包括的都不可能
				if(array[qMax.getFirst()] - array[qMin.getFirst()] > sum){
					break;
				}
			}
			//i要向前移，如果i是最大或最小要出队
			if(qMin.peekFirst() == i){
				qMin.pollFirst();
			}
			if(qMax.peekFirst() == i){
				qMax.pollFirst();
			}
			result += j - i;
		}
		return result;
	}

}
